#include <iostream>
#include <vector>
#include <unordered_map>
#include <random>
#include <unordered_set>
#include <algorithm>

using namespace std;

//剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器
//https://leetcode.cn/problems/FortPu/

/*
class RandomizedSet {
public:
    RandomizedSet(){
        srand((unsigned) time(nullptr));
    }

    bool insert(int val) {
        if (_map.count(val))
            return false;
        size_t index = _v.size();
        _v.push_back(val);
        _map[val] = index;
        return true;
    }

    bool remove(int val) {
        if (!_map.count(val))
            return false;
        int index = _map[val];
        _v[index] = _v.back();
        _map[_v.back()] = index;
        _v.pop_back();
        _map.erase(val);
        return true;
    }

    int getRandom() {
        int random = rand() % _v.size();
        return _v[random];
    }
private:
    unordered_map<int, int> _map;
    vector<int> _v;
};
*/

/*
int main() {
    RandomizedSet tmp;
    tmp.insert(0);
    tmp.insert(1);
    cout << tmp.remove(0) << endl;
    tmp.insert(2);
    cout << tmp.remove(1) << endl;
    cout << tmp.getRandom() << endl;
    return 0;
}
*/

/*int main(){
    std::random_device rd;
    std::mt19937 gen(rd());
    uniform_int_distribution<unsigned> u(0,9);
    cout << u(gen) << endl;
    return 0;
}*/

//242. 有效的字母异位词
//https://leetcode.cn/problems/valid-anagram/


/*
class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length())
            return false;
        vector<int> v(26,0);
        for (auto& ch : s) {
            v[ch - 'a']++;
        }
        for (auto& ch : t) {
            v[ch - 'a']--;
            if (v[ch - 'a'] < 0)
                return false;
        }
        return true;
    }
};
*/

/*
class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length() || s == t)
            return false;
        unordered_map<string, vector<string>> ret;
        string str = s;
        sort(str.begin(), str.end());
        ret[str].push_back(s);
        str = t;
        sort(str.begin(), str.end());
        ret[str].push_back(t);
        if (ret.size() != 1)
            return false;
        return true;
    }
};
*/

/*
int main(){
    string s1 = "ate";
    string s2 = "ata";
    Solution().isAnagram(s1, s2);
    return 0;
}
*/

//剑指 Offer II 033. 变位词组
//https://leetcode.cn/problems/sfvd7V/?envType=study-plan-v2&envId=coding-interviews-special

/*
class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length())
            return false;
        vector<int> v(26,0);
        for (auto& ch : s) {
            v[ch - 'a']++;
        }
        for (auto& ch : t) {
            v[ch - 'a']--;
            if (v[ch - 'a'] < 0)
                return false;
        }
        return true;
    }

    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ret;
        if (strs.empty())
            return ret;
        while (!strs.empty()){
            vector<string> v;
            string tmp = strs.back();
            auto it = strs.begin();
            while (it != strs.end()){
                if (isAnagram(*it, tmp)){
                    v.push_back(*it);
                    strs.erase(it);
                    --it;
                }
                ++it;
            }
            ret.push_back(v);
        }
        return ret;
    }
};
*/
//上述方法数据过多时不可行

/*
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>>mp;
        for(auto & i : strs){
            string str = i;
            sort(str.begin(),str.end());
            mp[str].push_back(i);
        }

        vector<vector<string>> ret;
        for(auto & it : mp){
            ret.push_back(it.second);
        }
        return ret;
    }
};
*/


/*
int main(){
    vector<string> str;
    str.push_back("eat");
    str.push_back("ate");
    str.push_back("tea");
    str.push_back("bat");
    vector<vector<string>> ret = Solution().groupAnagrams(str);
    return 0;
}
*/

//953. 验证外星语词典
//https://leetcode.cn/problems/verifying-an-alien-dictionary/

class Solution {
public:
    static bool less(string& a, string& b, string& order) {
        int minLen = min(a.size(), b.size());
        for (int i = 0; i < minLen; i++) {
            if (order.find(a[i]) < order.find(b[i]))
                return true;
            else if (order.find(a[i]) > order.find(b[i]))
                return false;
        }
        if (minLen == a.size())
            return true;
        else
            return false;
    }

    bool isAlienSorted(vector<string>& words, string order) {
        for (int i = 0; i < words.size() - 1; i++) {
            if (!less(words[i], words[i + 1], order)) return false;
        }
        return true;
    }
};
